# Copyright 2007 Boris Dusek
#
# This file is part of grapy.
#
# Grapy is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, version 3 of the License.
#
# Grapy is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Grapy.  If not, see <http://www.gnu.org/licenses/>.

from grapy.DFSHooks import *
from AdjListGraph import *
from Graph import *


class StronglyConnectedComponentsDFSHooks(DFSHooks):

    dep=[CoreDFSHooks]

    @staticmethod
    def dfs_main_begin(environ):
        environ.scc = {}

    @staticmethod
    def dfs_main_vertices_order(environ,vertices):
        environ.scc_count = 0
        reverse = dict([tuple(reversed(item)) for item in
            environ.first_f.iteritems()])
        for time in reversed(sorted(reverse)):
            yield reverse[time]

    @staticmethod
    def dfs_main_visit_invoke_before(environ,u):
        environ.scc_count += 1

    @staticmethod
    def dfs_visit_begin(environ,u):
        environ.scc[u] = environ.scc_count


def strongly_connected_components(g,dfs_first_environ=None):
    gT = AdjListGraph()
    gT.init_from_graph(g)
    gT.transpose()

    if not dfs_first_environ:
        dfs_hooks=DFSHooksSuite([],core=True)
        dfs_hooks.resolve_deps()
        dfs_first_environ = g.DFS(dfs_hooks)

    dfs_hooks = DFSHooksSuite([StronglyConnectedComponentsDFSHooks])
    dfs_hooks.resolve_deps()
    dfs_environ = DFSEnvironment()
    dfs_environ.first_f = dfs_first_environ.f
    gT.DFS(dfs_hooks,dfs_environ)
    return dfs_environ.scc
